<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
<meta name="viewport"
      content="width=device-width, initial-scale=1.0, maximum-scale=1.0, minimum-scale=1.0">
<meta http-equiv="X-UA-Compatible" content="ie=edge">

    <meta name="author" content="Mouweng">





<title>InnoDB存储引擎索引 | Mouweng&#39;s Blog</title>



    <link rel="icon" href="/favicon.ico">




    <!-- stylesheets list from _config.yml -->
    
    <link rel="stylesheet" href="/css/style.css">
    



    <!-- scripts list from _config.yml -->
    
    <script src="/js/script.js"></script>
    
    <script src="/js/tocbot.min.js"></script>
    



    
    
        
    


<meta name="generator" content="Hexo 5.1.1"><link rel="alternate" href="/atom.xml" title="Mouweng's Blog" type="application/atom+xml">
</head>
<body>
    <div class="wrapper">
        <header>
    <nav class="navbar">
        <div class="container">
            <div class="navbar-header header-logo"><a href="/">Mouweng</a></div>
            <div class="menu navbar-right">
                
                    <a class="menu-item" href="/archives">Posts</a>
                
                    <a class="menu-item" href="/category">Categories</a>
                
                    <a class="menu-item" href="/tag">Tags</a>
                
                    <a class="menu-item" href="/about">About</a>
                
                <input id="switch_default" type="checkbox" class="switch_default">
                <label for="switch_default" class="toggleBtn"></label>
            </div>
        </div>
    </nav>

    
    <nav class="navbar-mobile" id="nav-mobile">
        <div class="container">
            <div class="navbar-header">
                <div>
                    <a href="/">Mouweng</a><a id="mobile-toggle-theme">·&nbsp;Light</a>
                </div>
                <div class="menu-toggle" onclick="mobileBtn()">&#9776; Menu</div>
            </div>
            <div class="menu" id="mobile-menu">
                
                    <a class="menu-item" href="/archives">Posts</a>
                
                    <a class="menu-item" href="/category">Categories</a>
                
                    <a class="menu-item" href="/tag">Tags</a>
                
                    <a class="menu-item" href="/about">About</a>
                
            </div>
        </div>
    </nav>

</header>
<script>
    var mobileBtn = function f() {
        var toggleMenu = document.getElementsByClassName("menu-toggle")[0];
        var mobileMenu = document.getElementById("mobile-menu");
        if(toggleMenu.classList.contains("active")){
           toggleMenu.classList.remove("active")
            mobileMenu.classList.remove("active")
        }else{
            toggleMenu.classList.add("active")
            mobileMenu.classList.add("active")
        }
    }
</script>
        <div class="main">
            <div class="container">
    
    
        <div class="post-toc">
    <div class="tocbot-list">
    </div>
    <div class="tocbot-list-menu">
        <a class="tocbot-toc-expand" onclick="expand_toc()">Expand all</a>
        <a onclick="go_top()">Back to top</a>
        <a onclick="go_bottom()">Go to bottom</a>
    </div>
</div>

<script>
    document.ready(
        function () {
            tocbot.init({
                tocSelector: '.tocbot-list',
                contentSelector: '.post-content',
                headingSelector: 'h1, h2, h3, h4, h5',
                collapseDepth: 1,
                orderedList: false,
                scrollSmooth: true,
            })
        }
    )

    function expand_toc() {
        var b = document.querySelector(".tocbot-toc-expand");
        tocbot.init({
            tocSelector: '.tocbot-list',
            contentSelector: '.post-content',
            headingSelector: 'h1, h2, h3, h4, h5',
            collapseDepth: 6,
            orderedList: false,
            scrollSmooth: true,
        });
        b.setAttribute("onclick", "collapse_toc()");
        b.innerHTML = "Collapse all"
    }

    function collapse_toc() {
        var b = document.querySelector(".tocbot-toc-expand");
        tocbot.init({
            tocSelector: '.tocbot-list',
            contentSelector: '.post-content',
            headingSelector: 'h1, h2, h3, h4, h5',
            collapseDepth: 1,
            orderedList: false,
            scrollSmooth: true,
        });
        b.setAttribute("onclick", "expand_toc()");
        b.innerHTML = "Expand all"
    }

    function go_top() {
        window.scrollTo(0, 0);
    }

    function go_bottom() {
        window.scrollTo(0, document.body.scrollHeight);
    }

</script>
    

    
    <article class="post-wrap">
        <header class="post-header">
            <h1 class="post-title">InnoDB存储引擎索引</h1>
            
                <div class="post-meta">
                    
                        Author: <a itemprop="author" rel="author" href="/">Mouweng</a>
                    

                    
                        <span class="post-time">
                        Date: <a href="#">August 26, 2020&nbsp;&nbsp;23:41:12</a>
                        </span>
                    
                    
                        <span class="post-category">
                    Category:
                            
                                <a href="/categories/mysql/">mysql</a>
                            
                        </span>
                    
                </div>
            
        </header>

        <div class="post-content">
            <h2 id="一、B-树索引"><a href="#一、B-树索引" class="headerlink" title="一、B+树索引"></a>一、B+树索引</h2><blockquote>
<p>B+树索引可以分为<strong>聚集索引</strong>和<strong>辅助索引</strong>。他们的不同是<strong>叶子结点是否存放一整行的信息</strong>。</p>
</blockquote>
<h3 id="1-聚集索引"><a href="#1-聚集索引" class="headerlink" title="1.聚集索引"></a>1.聚集索引</h3><blockquote>
<p>按照每张表的主键构建一棵B+树，同时叶子结点中存放的即为整张表的行记录数据，叶子结点（数据页）通过双向链表进行连接。</p>
<p>InnoDB存储引擎表就是索引组织表，每张表只能拥有一个聚集索引，但可以有多个辅助索引。</p>
</blockquote>
<h4 id="说明"><a href="#说明" class="headerlink" title="说明"></a>说明</h4><ul>
<li><p>多数情况下，查询优化器 倾向于使用聚集索引，因为可以直接在叶子结点上找到数据。</p>
</li>
<li><p>由于定义了数据的逻辑顺序，聚集索引能够特别快地访问针对范围值的查询，也就是对于主键的排序查找和范围查找来说速度非常快。</p>
</li>
</ul>
<h3 id="2-辅助索引"><a href="#2-辅助索引" class="headerlink" title="2.辅助索引"></a>2.辅助索引</h3><blockquote>
<p>叶子结点并不包含行记录数据的全部数据。</p>
<p>叶子节点包含辅助索引键值和书签（primary key）。</p>
<p>由于InnoDB存储引擎表是索引组织表，所以书签就是相应行数据的聚集索引键。</p>
</blockquote>
<h4 id="原理"><a href="#原理" class="headerlink" title="原理"></a>原理</h4><p>​    当通过辅助索引来寻找数据时，InnoDB存储引擎会遍历辅助索引并通过叶级别的指针获得指向主键索引的主键，然后再通过主键索引来找到一个完整的行记录。</p>
<h4 id="举例"><a href="#举例" class="headerlink" title="举例"></a>举例</h4><p>​    如果在一棵高度为3的辅助索引树中查找数据，需要对这棵辅助索引树做3次IO操作找到指定的书签（主键）；如果聚集索引树的高度同样为3，那么还需要对聚集索引进行3次I/O，找到完整行数所在的数据页。一共需要6次IO操作。</p>
<h2 id="二、Cardinality值"><a href="#二、Cardinality值" class="headerlink" title="二、Cardinality值"></a>二、Cardinality值</h2><h3 id="1-Cardinality的意义"><a href="#1-Cardinality的意义" class="headerlink" title="1.Cardinality的意义"></a>1.Cardinality的意义</h3><blockquote>
<p>表示索引中不重复记录数量的预估值。</p>
</blockquote>
<h4 id="高选择性"><a href="#高选择性" class="headerlink" title="高选择性"></a>高选择性</h4><p>​    在访问表中高选择性数据时使用B+树索引才有意义。例如性别、地区、类型字段可取值范围很小，选择性很低。</p>
<p>​    Cardinality / n_row_in_table 要尽可能小，否则索引没必要建立。</p>
<h3 id="2-Cardinality的统计"><a href="#2-Cardinality的统计" class="headerlink" title="2.Cardinality的统计"></a>2.Cardinality的统计</h3><blockquote>
<p>InnoDB对于Cardinality的统计是通过采样进行的,所以不是精确值。</p>
</blockquote>
<h4 id="原因"><a href="#原因" class="headerlink" title="原因"></a>原因</h4><p>​    生产环境中，索引的更新操作是非常频繁的，且对于数据量很大的表，如果每次更新都要进行Cardinality的统计所需的时间很长，给数据库带来很大复旦，因此通过采样方式。</p>
<h4 id="更新策略"><a href="#更新策略" class="headerlink" title="更新策略"></a>更新策略</h4><p>​    INSERT和UPDATE时更新Cardinality。策略为：</p>
<ul>
<li>表中1/16的数据发生变化;</li>
<li>变化次数stat_modified_counter&gt;2000000000;</li>
</ul>
<h4 id="采样过程"><a href="#采样过程" class="headerlink" title="采样过程"></a>采样过程</h4><ul>
<li>取得B+树索引中叶子结点的数量，记为A；</li>
<li>随机取得B+树索引中的8个叶子结点。统计每个页不同记录的个数，为P1,P2,..,P8;</li>
<li>根据采样信息给出Cardinality的预估值 = (P1+P+..+P8)*A/8;</li>
</ul>
<h4 id="说明-1"><a href="#说明-1" class="headerlink" title="说明"></a>说明</h4><p>​    每次统计得到的Cardinality值不一定相同。</p>
<p>​    当索引的B+树叶子结点个数小于等于8个时，每次得到的Cardinality值相同。</p>
<h2 id="三、B-树索引的使用"><a href="#三、B-树索引的使用" class="headerlink" title="三、B+树索引的使用"></a>三、B+树索引的使用</h2><h3 id="1-联合索引"><a href="#1-联合索引" class="headerlink" title="1.联合索引"></a>1.联合索引</h3><blockquote>
<p>对表上的多个列进行索引</p>
</blockquote>
<figure class="highlight sql"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">CREATE</span> <span class="keyword">TABLE</span> t (</span><br><span class="line">	a <span class="built_in">INT</span>,</span><br><span class="line">  b <span class="built_in">INT</span>,</span><br><span class="line">  <span class="keyword">KEY</span> idx_a_b (a,b)</span><br><span class="line">)<span class="keyword">ENGINE</span>=<span class="keyword">INNODB</span></span><br><span class="line"><span class="comment">/* 先按照a值进行排序，再按照b值进行排序 */</span></span><br></pre></td></tr></table></figure>

<h4 id="使用情况"><a href="#使用情况" class="headerlink" title="使用情况"></a>使用情况</h4><ul>
<li>对于WHERE a=xxx AND b=xxx 可以使用这个索引</li>
<li>对于WHERE a=xxx 也可以使用这个索引</li>
<li>对于WHERE b=xxx 则不可以使用</li>
</ul>
<h4 id="优点"><a href="#优点" class="headerlink" title="优点"></a>优点</h4><p>​    已经对第二个键值进行了排序，很多时候应用程序都需要查询某个用户的购物情况，并按照时间进行排序，使用联合索引可以避免多一次的排序操作。</p>
<h3 id="2-覆盖索引"><a href="#2-覆盖索引" class="headerlink" title="2.覆盖索引"></a>2.覆盖索引</h3><blockquote>
<p>从辅助索引中就可以得到查询记录，不需要查询聚集索引中的记录。</p>
</blockquote>
<h4 id="原理-1"><a href="#原理-1" class="headerlink" title="原理"></a>原理</h4><p>​    对于InnoDB存储引擎的辅助索引而言，由于其包含了主键信息，因此其叶子结点存放的数据为（primary key1, primary key2, …, key1, key2, … ）。故查询SELECT x FROM table where y=xxx;（只要x和y在辅助索引椰子结点数据内，都可以使用一次辅助联合索引完成）</p>
<figure class="highlight sql"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">SELECT</span> primary key1, primary key2, key2 <span class="keyword">FROM</span> t <span class="keyword">WHERE</span> key1=xxx;</span><br></pre></td></tr></table></figure>

<h4 id="优点-1"><a href="#优点-1" class="headerlink" title="优点"></a>优点</h4><ul>
<li>进行一次辅助联合索引加快查询速度</li>
<li>对于某些统计问题而言，不会通过聚集索引来进行统计，而会选择辅助索引减少IO操作，一般来说辅助索引数据量小，每一页可以存放的内容多，故树高小，IO效率高。</li>
</ul>
<h3 id="3-优化器选择不使用索引"><a href="#3-优化器选择不使用索引" class="headerlink" title="3.优化器选择不使用索引"></a>3.优化器选择不使用索引</h3><blockquote>
<p>某些情况，优化器并没有选择索引去查找数据，而是通过扫描聚集索引，也就是直接进行全表的扫描来得到数据。这种情况多发于范围查找、JOIN链接操作等情况下。</p>
</blockquote>
<h4 id="原理-2"><a href="#原理-2" class="headerlink" title="原理"></a>原理</h4><p>​    <strong>对于不能进行索引覆盖的情况，优化器选择辅助索引的情况是 : 通过辅助索引查找的数据是少量的。</strong></p>
<p>​    数据量大的情况下，进行大量数据的范围查找，虽然辅助索引上，数据是有序的，但是 因为不能索引覆盖，所以要再次书签访问来查找聚集索引上的整行数据信息，这时候就变为离散读操作，因为顺序读要远快于离散读，所以直接扫描聚集索引。</p>
<h3 id="4-MRR优化"><a href="#4-MRR优化" class="headerlink" title="4.MRR优化"></a>4.MRR优化</h3><blockquote>
<p>​    Muliti-Range Read优化的目的是为了减少磁盘的随机访问，并且将随机访问转化为较为顺序的数据访问，适用于range， ref， eq_ref。</p>
</blockquote>
<h4 id="工作方式"><a href="#工作方式" class="headerlink" title="工作方式"></a>工作方式</h4><p>​    在查询辅助索引时，首先根据得到的查询结果，按照主键进行排序，并按照主键排序的顺序进行书签查找。</p>
<h4 id="优点-2"><a href="#优点-2" class="headerlink" title="优点"></a>优点</h4><ul>
<li>可以减少缓冲池中页被替换的次数</li>
<li>批量处理对键值的查询操作。</li>
<li>查询性能得到极大的提高</li>
</ul>
<h3 id="5-ICP优化"><a href="#5-ICP优化" class="headerlink" title="5.ICP优化"></a>5.ICP优化</h3><blockquote>
<p>取出索引的同时，判断是否可以进行WHERE条件查询，将WHERE的部分过滤操作放在存储引擎层，在某些查询下，可以大大减少上层SQL层对记录的索取，提高数据库整体性能。</p>
</blockquote>
<h2 id="四、哈希索引"><a href="#四、哈希索引" class="headerlink" title="四、哈希索引"></a>四、哈希索引</h2><p>哈希索引能以 O(1) 时间进行查找，但是失去了有序性：</p>
<ul>
<li>无法用于排序与分组；</li>
<li>只支持精确查找，无法用于部分查找和范围查找。</li>
</ul>
<p>InnoDB 存储引擎有一个特殊的功能叫“<strong>自适应哈希索引</strong>”，当某个索引值被使用的非常频繁时，会在 B+Tree 索引之上再创建一个哈希索引，这样就让 B+Tree 索引具有哈希索引的一些优点，比如快速的哈希查找。</p>
<h2 id="五、全文检索"><a href="#五、全文检索" class="headerlink" title="五、全文检索"></a>五、全文检索</h2><blockquote>
<p>将存储于数据库的整篇文章中的任意内容信息查找出来的技术。</p>
</blockquote>
<h3 id="1-倒排索引"><a href="#1-倒排索引" class="headerlink" title="1.倒排索引"></a>1.倒排索引</h3><blockquote>
<p>在辅助表中存储了单词与单词自身在一个或多个文档中所在位置之间的映射。</p>
</blockquote>
<ul>
<li>inverted file index，其表现形式为{单词，单词所在文档的ID}</li>
<li>full inverted inndex，其表现形式为{单词 , (单词所在文档的ID , 在文档中的具体位置)}</li>
</ul>
<h3 id="2-InnoDB全文检索"><a href="#2-InnoDB全文检索" class="headerlink" title="2.InnoDB全文检索"></a>2.InnoDB全文检索</h3><p>（具体的细节回顾MySQL技术内幕InnoDB存储引擎）</p>
<blockquote>
<p>InnoDB存储引擎从1.2.x版本开始支持全文检索的技术，其采用Full inverted index的方式。</p>
</blockquote>
<h4 id="原理-3"><a href="#原理-3" class="headerlink" title="原理"></a>原理</h4><ul>
<li>InnoDB的全文检索表中有两个列：( word, ilist )，ilist=(DocumentID, Position)，其中word字段上设有索引。</li>
<li>Auxiliary Table为辅助表，还设有红黑树结构实现的FTS Index Cache缓存，来提高全文检索的性能</li>
<li>查找条件使用 MATCH AGAINST，而不是普通的 WHERE。</li>
</ul>

        </div>

        
            <section class="post-copyright">
                
                
                
                

            </section>
        
        <section class="post-tags">
            <div>
                <span>Tag(s):</span>
                <span class="tag">
                    
                    
                        <a href="/tags/InnoDB/"># InnoDB</a>
                    
                        <a href="/tags/%E7%B4%A2%E5%BC%95/"># 索引</a>
                    
                        
                </span>
            </div>
            <div>
                <a href="javascript:window.history.back();">back</a>
                <span>· </span>
                <a href="/">home</a>
            </div>
        </section>
        <section class="post-nav">
            
                <a class="prev" rel="prev" href="/2020/08/26/InnoDB%E9%94%81%E7%9A%84%E5%AE%9E%E7%8E%B0/">InnoDB锁的实现</a>
            
            
            <a class="next" rel="next" href="/2020/08/26/git/">Git版本控制工具</a>
            
        </section>


    </article>
</div>

        </div>
        <footer id="footer" class="footer">
    <div class="copyright">
        <span>© Mouweng | Powered by <a href="https://hexo.io" target="_blank">Hexo</a> & <a href="https://github.com/Siricee/hexo-theme-Chic" target="_blank">Chic</a></span>
    </div>
</footer>

    </div>
</body>
</html>
